package java学习.算法.二叉树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/10 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 把二叉树打印成多行 {
//  双队列 ，
    ArrayList<ArrayList<Integer>> Print1(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (pRoot==null){
            return  res;
        }
        LinkedList<TreeNode> stack1 = new LinkedList<>();
        LinkedList<TreeNode> stack2 = new LinkedList<>();

        stack1.push(pRoot);
        int cur = 1;
        while (!stack1.isEmpty()||!stack2.isEmpty()){
            if (cur % 2 != 0) {
                ArrayList<Integer> list = new ArrayList<>();
                while (!stack1.isEmpty()){
                    TreeNode pop = stack1.pop();
                    list.add(pop.val);

                    if (pop.left!=null){
                        stack2.push(pop.left);
                    }
                    if (pop.right!=null){
                        stack2.push(pop.right);
                    }
                }
                if (list!=null){
                    cur++;
                    res.add(list);
                }
            }else {
                ArrayList<Integer> list2 = new ArrayList<>();

                while (!stack2.isEmpty()){
                    TreeNode pop = stack2.pop();
                    list2.add(pop.val);

                    if (pop.left!=null){
                        stack1.push(pop.left);
                    }
                    if (pop.right!=null){
                        stack1.push(pop.right);
                    }
                }
                if (list2!=null){
                    cur++;
                    res.add(list2);
                }
            }

        }
        return  res;

    }
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();

        if (pRoot==null){
            return  res;
        }
        int curNum = 1; // 当前层个数
        int nextNum = 0;  //  下一层的个数
        LinkedList<TreeNode> queue = new LinkedList<>();

        queue.add(pRoot);
        while (!queue.isEmpty()){
            TreeNode pop = queue.pop();
            list.add(pop.val);
            curNum--;
            if (pop.left!=null){
                queue.push(pop.left);
                nextNum++;
            }
            if (pop.right!=null){
                queue.push(pop.right);
                nextNum++;
            }
            if (curNum==0){
                res.add(list);
                list = new ArrayList<>();
                curNum = nextNum;
            }

        }
        return  res;
    }

}
